#define noDATA_ENTITY_CLASS_NAME PowerEntity
#define noDATA_DATABASE_CLASS_NAME PowerDatabase

#define DATA_ENTITY_CLASS_NAME ImageEntity
#define DATA_DATABASE_CLASS_NAME ImageDatabase

#ifndef CLUSTERING
#define CLUSTERING

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <list>
#include "hyperspace.h"
#include "denclue_functions.h"
#include "DataImage.h"


using namespace std;

class HyperSpace;
class DenclueFunctions;

class Cluster {
    public:
        unsigned int id;
        list<DATA_ENTITY_CLASS_NAME*> items;

        Cluster(unsigned int id){
            this->id = id;
        }

        void toString(){
            printf("id:%d size:%d\n",
                   id, items.size()
            );
        }

        unsigned int getId(){
            return id;
        }

        void insert(DATA_ENTITY_CLASS_NAME *one){
            items.push_back(one);
        }
};

class Clustering {
    public:
        DATA_DATABASE_CLASS_NAME *pdb;
        list<Cluster> clusters;
        double epsilon;
        unsigned int minpts;

        Clustering(DATA_DATABASE_CLASS_NAME *pdb){
            this->pdb = pdb;
            this->epsilon = 0;
            this->minpts = 0;
        }

        void dbscan(double epsilon, unsigned int minpts){
            unsigned int i;
            DATA_ENTITY_CLASS_NAME *one;
            Cluster *c;
            list<Cluster>::iterator it;

            this->epsilon = epsilon;
            this->minpts = minpts;

            for(i=0; i<pdb->getSize(); ++i){
                one = &pdb->db[i];
                if (one->getClusterId()==CLUSTER_UNCLASSIFIED){
                    c = newCluster();
                    if (expandCluster(c, one)){
                        c->toString();
                    } else {
                        popCluster();
                    }
                }
            }

        }

        Cluster* newCluster(){
            Cluster *nc = new Cluster(clusters.size());
            clusters.push_back(*nc);
            return nc;
        }

        void popCluster(){
            clusters.pop_back();
        }

        int expandCluster(Cluster *c, DATA_ENTITY_CLASS_NAME *startObject){
            assert(c);
            assert(epsilon>0);

            list<DATA_ENTITY_CLASS_NAME*>* seeds;
            list<DATA_ENTITY_CLASS_NAME*>* neighborhood;
            DATA_ENTITY_CLASS_NAME *one;
            DATA_ENTITY_CLASS_NAME *two;

            seeds = pdb->getEpsilonNeighborhood(startObject, epsilon);

            if (seeds->size() < minpts){
                startObject->setClusterId(CLUSTER_NOISE);
                return 0;
            }

            // startObject is a core object
            list<DATA_ENTITY_CLASS_NAME*>::iterator it;
            for( it=seeds->begin(); it!=seeds->end(); ++it ){
                (*it)->setClusterId(c->getId());
                c->insert(*it);
            }

            seeds->remove(startObject);

            while (seeds->size() != 0){
                one = seeds->front();
                neighborhood = pdb->getEpsilonNeighborhood(one, epsilon);
                if (neighborhood->size()>=minpts){
                    // one is a core object
                    for( it=neighborhood->begin(); it!=neighborhood->end(); ++it ){
                        two = *it;
                        if ((two->getClusterId() == CLUSTER_UNCLASSIFIED)||(two->getClusterId() == CLUSTER_NOISE)){
                            if (two->getClusterId() == CLUSTER_UNCLASSIFIED){
                                seeds->push_back(two);
                            }
                            two->setClusterId(c->getId());
                            c->insert(two);
                        }
                    }
                }
                seeds->remove(one);
                delete neighborhood;
            }
            return 1;
        }

        void toString(){
            list<Cluster>::iterator it;
            printf("CLUSTER eps:%lf minpts:%d\n", epsilon, minpts);
            for( it=clusters.begin(); it!=clusters.end(); ++it ){
                it->toString();
            }
        }

        /// DENCLUE

        void denclue(double sigma, double xi)
        {
            unsigned int i;
            const vector<unsigned int>& upper_bounds = pdb->retrieveUpperBound();
            const vector<unsigned int>& lower_bounds = pdb->retrieveLowerBound();
            HyperSpace spatial_region( upper_bounds, lower_bounds, sigma, xi, 2);
            spatial_region.determineSpatialRegions();
            cout << "HyperSpace defined, inserting entities" << endl;
            for(i=0; i<pdb->getSize(); ++i){
                spatial_region.insertEntity(pdb->db[i]);
            }
            cout << "Removing low populated hypercubes" << endl;
            spatial_region.removeLowPopulatedHypercubes();
            cout << "Entities inserted, calculating density functions at each entity"
                << endl;
            HyperSpace::EntityIterator hs_iter(spatial_region);
            for( hs_iter.begin() ; !hs_iter.end() ; hs_iter++){
                //cout << "starting1" << endl;
                //cout << "starting2" << endl;
                HyperSpace::EntityIterator calculation_iter(spatial_region);
                calculation_iter.begin();
                //cout << "starting3" << endl;
                double curr_density = DenclueFunctions::calculateDensity( *hs_iter , calculation_iter, sigma );
                //cout << "starting4" << endl;
                hs_iter->setDensity( curr_density );
            }
            cout << "Densities calculated, determining density-attractors" << endl;
            map< string, vector<DATA_ENTITY_CLASS_NAME> > clusters;
            HyperSpace::EntityIterator iter_entities(spatial_region);
            iter_entities.begin();
            unsigned long whileiter = 0;
            while( !iter_entities.end() ){
                //cout << whileiter++ << endl;
                HyperSpace::EntityIterator attractor_entity_iter(spatial_region);
                attractor_entity_iter.begin();
                DATA_ENTITY_CLASS_NAME curr_attractor =
                    DenclueFunctions::getDensityAttractor(*iter_entities,
                            spatial_region, attractor_entity_iter , sigma);
                //cout << "denattr " << curr_attractor.x << ","<< curr_attractor.y << endl;
                if( curr_attractor.getDensity() < xi ){
                    iter_entities++;
                    continue;
                }
                if( clusters.count( curr_attractor.getStringRepresentation() ) <= 0 ){
                    vector<DATA_ENTITY_CLASS_NAME> *vec = new vector<DATA_ENTITY_CLASS_NAME>();
                    clusters.insert( make_pair(curr_attractor.getStringRepresentation(), *vec) );
                }
                clusters[curr_attractor.getStringRepresentation()].push_back(*iter_entities);
                iter_entities++;
            }
            cout << "Density attractors determined, determining clusters" << endl;
            map< string, vector<DATA_ENTITY_CLASS_NAME> >::iterator outer_iter = clusters.begin();
            while( outer_iter != clusters.end() ){
                map< string, vector<DATA_ENTITY_CLASS_NAME> >::iterator inner_iter = outer_iter;
                inner_iter++;
                while( inner_iter != clusters.end() ){
                    ostringstream outer_str;
                    ostringstream inner_str;
                    outer_str << outer_iter->first << '\n';
                    inner_str << inner_iter->first << '\n';
                    DATA_ENTITY_CLASS_NAME outer;
                    DATA_ENTITY_CLASS_NAME inner;
                    outer.entityFromString( outer_str.str() );
                    inner.entityFromString( inner_str.str() );

                    map<string, bool> usedEntities;
                    usedEntities[inner.getStringRepresentation()] = true;
                    usedEntities[outer.getStringRepresentation()] = true;

                    bool canMerge = DenclueFunctions::pathBetweenExists( outer, inner, spatial_region, xi, sigma, usedEntities);


                    if( canMerge ){
                        DenclueFunctions::AppendVector( outer_iter->second , inner_iter->second );
                        clusters.erase( inner_iter++ );
                        continue;
                    }
                    inner_iter++;
                }
                outer_iter++;
            }
            /// print output
            map< string, vector<DATA_ENTITY_CLASS_NAME> >::const_iterator iter = clusters.begin();
            unsigned int newsize = 0;
            unsigned ind_cluster = 0;
            DATA_ENTITY_CLASS_NAME newdb[pdb->getSize()];
            while( iter != clusters.end() ){
                if( iter->second.empty() ){
                    iter++;
                    continue;
                }
                cout << "Cluster " << ind_cluster << "\tAttractor " << iter->first << endl;

                vector<DATA_ENTITY_CLASS_NAME>::const_iterator ent_iter = iter->second.begin();
                for( ; ent_iter != iter->second.end() ; ent_iter++){
                    cout << '\t' << ent_iter->x << ',' << ent_iter->y << endl;
                    newdb[newsize].x = ent_iter->x;
                    newdb[newsize].y = ent_iter->y;
                    newdb[newsize].setClusterId(ind_cluster);
                    ++newsize;
                }
                ++ind_cluster;
                iter++;
            }
            memcpy(pdb->db, newdb, pdb->getSize()*sizeof(DATA_ENTITY_CLASS_NAME));
            pdb->setSize(newsize);
        }
};

#endif
